COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input acphdr % Section 3.3
C00003 00003	\ninepoint
C00005 00004	\ansno 33. Let $K↓n$ be the set of all such $n$-digit numbers, so that
C00012 ENDMK
C⊗;
\input acphdr % Section 3.3
\open0=tmp.inx
\runninglefthead{RANDOM NUMBERS} % chapter title
\titlepage\setcount00
\null
\vfill
\tenpoint
\ctrline{some silly test for THE ART OF COMPUTER PROGRAMMING}
\ctrline{$\copyright$ 1980 Addison--Wesley Publishing Company, Inc.}
\vfill
\runningrighthead{THE SILLY TEST}
\section{9.9.9}
\eject
\setcount0 901
\ninepoint
\ansno 14. \save7\hbox to 329pt{$\def\\{\hskip 4.5pt}\hskip0pt plus 200pt
\eqalign{\vbox to 8pt{}1\\1\\3\\2\\1⊗\qquad[5-4i]\cr
1\\1\\3\\2\\1⊗\qquad[5-4i]\cr
\noalign{\vskip -7.6pt}
\vbox{\hrule width 40.5pt}\cr
\noalign{\vskip-1.75pt}
1\\1\\3\\2\\1\cr
1\\1\\2\\0\\2\\\\\cr
1\\2\\1\\2\\3\\\\\\\\\cr
1\\1\\3\\2\\1\\\\\\\\\\\\\cr
1\\1\\3\\2\\1\\\\\\\\\\\\\\\\\cr
\noalign{\vskip 3pt\hrule width 76.5pt\vskip 3pt}
0\\1\\0\\3\\1\\1\\2\\0\\1⊗\qquad[9-40i]\cr}\hskip0pt plus 200pt$}\!
\raise 8pt\hbox{\lower 1ht7\box7}

\ansno 15. $[-{10\over 11}, {1\over 11}]$, and the rectangle
shown in Fig.\ A--6.

\vfill\end
\ansno 33. Let $K↓n$ be the set of all such $n$-digit numbers, so that
$k↓n=\|K↓n\|$. If $S$ and $T$ are any finite sets of integers, we shall say
$S~T$ if $S=T+x$ for some integer $x$, and we shall write $k↓n(S)=\|\Kscr↓n(S)\|$,
where $\Kscr(S)$ is the family of all subsets of $K↓n$ that are $~S$. When
$n=0$, we have $k↓n(S)=0$ unless $\|S\|≤1$, since zero is the only ``0-digit''
number. When $n≥1$ and $S=\{s↓1,\ldotss,s↓r\}$, we have $$\twoline{\Kscr(S)=
\union↓{0≤j<b}\;\;\union↓{(a↓1,\ldotss,a↓r)}\left.
\mathopen{\vcenter{\hbox{\:@\char'10}}}\,
\{t↓1b+a↓1,\ldotss,t↓rb+a↓r\}\;\right|}{3pt}{\{t↓1,\ldotss,t↓r\}\in K↓{n-1}\biglp
\leftset(S↓i+j-a↓i)/b\relv1≤i≤r\rightset\bigrp\,\mathclose{\vcenter{
\hbox{\:@\char'11}}},}$$
where the inner union is over all sequences of digits $(a↓1,\ldotss,a↓r)$ such
that we have
$a↓i≡S↓i+j\modulo b$ for $1≤i≤r$. In this formula we require $t↓i-t↓{i↑\prime}
={(s↓i-a↓i)}/b-{(s↓{i↑\prime}-a↓{i↑\prime})}/b$ for $1≤i<i↑\prime≤r$, so that
the naming of subscripts is uniquely determined. By the principle of
\α{inclusion and exclusion}, therefore, we have $k↓n(S)=\sum↓{0≤j<b}\sum↓{m≥1}
(-1)↑{m-1}f(S,m,j)$, where $f(S,m,j)$ is the number of sets of integers that can
be expressed as $\{t↓1b+a↓1,\ldotss,t↓rb+a↓r\}$ in the above manner for $m$
different sequences $(a↓1,\ldotss,a↓r)$, summed over all choices of $m$ different
sequences $(a↓1,\ldotss,a↓r)$. Given $m$ different sequences $(a↓1↑{(l)},\ldotss,
a↓r↑{(l)})$ for $1≤l≤m$, the number of such sets is $k↓{n-1}\biglp\{(s↓i+j
-a↓i↑{(l)})/b\relv 1≤i≤r,1≤l≤m\}\bigrp$. Thus there is a collection of sets
$\Tscr(S)$ such that $$k↓n(S)=\sum↓{T\in\Tscr(S)}c↓T\,k↓{n-1}(T),$$
where each $c↓T$ is an integer. Furthermore if $T\in \Tscr(S)$ we have
$\min T≥(\min S-\max D)/b$ and $\max T≤(\max S+b-1-\min D)/b$. Thus we have
simultaneous recurrence relations for the sequences $\langle k↓n(S)\rangle$,
where $S$ is any nonempty integer subset of $[l,u+1]$ in the notation of
exercise↔19. Since $k↓n=k↓n(S)$ for any one-element set $S$, the sequence
$\langle k↓n\rangle$ appears these recurrences. The coefficients $c↓T$ can
be computed from the first few values of $k↓n(S)$, so we can obtain a system of
equations defining the generating functions $k↓S(z)=\sum k↓n(S)z↑n=
\biglp\|S\|≤1\bigrp+z\sum↓{T\in\Tscr(S)}c↓Tk↓T(z)$.

For example, when $D=\{-1,0,3\}$ and $b=3$ we have $l=-{3\over2}$ and $u={1\over2}$,
so the relevant sets $S$ are $\{0\}$, $\{0,1\}$, $\{-1,1\}$, and
$\{-1,0,1\}$. The corresponding sequences for $n≤3$ are $\langle1,3,8,21\rangle$,
$\langle0,1,3,8\rangle$, $\langle0,0,1,4\rangle$, and $\langle0,0,0,0\rangle$;
so we obtain
$$\eqalign{k↓0(z)⊗=1+z\biglp3k↓0(z)-k↓{01}(z)\bigrp,\cr
k↓{01}(z)⊗=zk↓0(z),\cr}\qquad\qquad
\eqalign{k↓{02}(z)⊗=z\biglp k↓{01}(z)+k↓{02}(z)\bigrp,\cr
l↓{012}(z)⊗=0,\cr}$$
and $k(z)=1/(1-3z+z↑2)$.
\inx{Fibonacci number}
In this case $k↓n=F↓{2n+2}$ and $k↓n\biglp\{0,2\}\bigrp=F↓{2n-1}-1$.